Codeforces Round 541 (Div. 2)

Diposting di | Edited on

传送门

A.Sea Battle (签到)

题意

给你一个上下两个矩形,让他们左边对着拼起来，求出他们外面一圈的面积

思路

关键就是中间那一块留面积大的就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=0;
    ans+=(a+2)*(b+1);


    ans+=(c+2)*(d+1);

    ans-=min(a+2,c+2);

    ans+=max(a+2,c+2);
    ans-=a*b+c*d;
    cout<<ans;
    return 0;
}

B.Draw! (模拟)

题意

按顺序给你一堆比分，问你最多能出现几场胜场

思路

也是直接模拟，不过要注意平局的时候

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll ans=1;
    int n;
    cin>>n;
    ll aa=0,bb=0;
    for(int i=1;i<=n;i++){
        ll a,b;
        cin>>a>>b;
        if(a<bb||b<aa){
            aa=a,bb=b;continue;
        }
        ans+=min(a,b)-max(aa,bb)+1;
        if(aa==bb)ans--;
        aa=a,bb=b;
    }
    cout<<ans;
    return 0;
}

C.Birthday (模拟)

题意

给你一堆高度，让你重新排成一个圆使得对于任意一个高度她周围的差尽可能小

思路

对于一个数，那么她周围的肯定是和他最近的数，所以直接排序一下，拿一个双端队列前后模拟一下就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    deque<int>dq;
    for(int i=1;i<=n;i++){
        if(i&1)
            dq.push_back(a[i]);
        else dq.push_front(a[i]);
    }
    for(int i=1;i<=n;i++){
        cout<<dq.front()<<" ";
        dq.pop_front();
    }
    return 0;
}

D.Gourmet choice (并查集缩点+拓扑排序)

题意

有N+M个数 给出他们之间两两的比较，让你构造出一组数据满足这个比较

思路

首先考虑’=’如果有=的话说明他们的值是一样的 所以可以把他们缩成一个点，可以减少计算量

然后对于‘>’和”<”其实我们都可以转化成’>’ 对于一个>我们可以变成一个图，表示>右边的那个数比左边的小，连小一条线，说明左边的要等右边的数字都分配完再分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m;
int fa[maxn],d[maxn],a[maxn];
vector<int>G[maxn];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
char s[2005][2005];
void add(int i,int j){
    int aa=find(i),bb=find(j);
    if(aa==bb)puts("No"),exit(0);
    d[aa]++;
    G[bb].push_back(aa);
}
int vis[maxn];
void topo(){
    queue<pair<int,int> >Q;
    for(int i=1;i<=n+m;i++){
        int aa=find(i);
        if(!d[aa]&&!vis[aa])Q.push(make_pair(aa,1)),vis[aa]=1;
    }
    while(!Q.empty()){
        pair<int,int> now=Q.front();Q.pop();
        int u=now.first;
        a[u]=max(a[u],now.second);
        for(auto i:G[u]){
            a[i]=max(a[u]+1,a[i]);
            d[i]--;
            if(!d[i])Q.push(make_pair(i,a[i]));
        }
    }
    for(int i=1;i<=n+m;i++)
        if(d[i])puts("No"),exit(0);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n+m;i++)fa[i]=i;
    for(int i=1;i<=n;i++){
        cin>>s[i]+1;
        for(int j=1;j<=m;j++){
            if(s[i][j]=='='){
                int aa=find(i),bb=find(j+n);
                fa[bb]=aa;
            }
           /* else if(s[j]=='>'){
                add(i,j+n);
            }
            else add(n+j,i);*/
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
        if(s[i][j]=='>')add(i,n+j);
        if(s[i][j]=='<')add(n+j,i);
        }
    topo();
    cout<<"Yes"<<endl;
    for(int i=1;i<=n;i++)cout<<a[find(i)]<<" ";cout<<endl;
    for(int j=1;j<=m;j++)cout<<a[find(j+n)]<<" ";
    return 0;
}
/*
3 3
<<<
<<=
<<=
*/

E.String Multiplication(DP)

题意

定义一种字符串乘法 如果aab*c变成cacacbc

就是用后一个字符串填满前一个字符串的空隙和前后

问你n个乘法过后的结果字符串的最长连续相同字母是多少

思路

可以发现答案又最后一种字符串控制，因为就算前面的答案是多少都会被最后一个字符串拆开

所以分析最后一个字符串，发现情况有三种

如果最后一个字符串字符只有一种，那么答案就为这个前面那个字符串的这个字符长度+1 并且乘上最后一个字符串的长度 + 前面那个字符串的长度

如果是 不是的话那么答案就只和最后字符串的前后字符有关系，答案就是当前字符串的前后最长长度+（前面的答案是否有包含这个字符） 如果前后的字符都一样的话那么答案又不同了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int dp[maxn][26],a[26],head,tail,ans;
char s[maxn];
void init(){
    memset(a,0,sizeof(a));
    int n=strlen(s+1),t=1;
    for(int i=2;i<=n;i++){
        if(s[i]!=s[i-1])
            a[s[i-1]-'a']=max(a[s[i-1]-'a'],t),t=1;
        else t++;
    }
    a[s[n]-'a']=max(a[s[n]-'a'],t);
    head=tail=1;
    for(int i=2;i<=n;i++)
        if(s[i]==s[i-1])head++;
        else break;
    for(int i=n-1;i>=1;i--)
        if(s[i]==s[i+1])tail++;
    else break;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s+1;
        int len=strlen(s+1);
        init();
        if(head==len){
            int k=s[1]-'a';
            dp[i][k]=head*(dp[i-1][k]+1)+dp[i-1][k];
        }
        for(int j=0;j<26;j++){
            dp[i][j]=max(dp[i][j],a[j]);
            if(dp[i-1][j]){
                dp[i][j]=max(dp[i][j],1);
                int p1=0,p2=0;
                if(s[1]==char('a'+j)){
                    p1=1;
                    dp[i][j]=max(dp[i][j],head+1);
                }
                if(s[len]==char('a'+j)){
                    p2=1;
                    dp[i][j]=max(dp[i][j],tail+1);
                }
                if(p1&&p2)dp[i][j]=max(dp[i][j],head+tail+1);
            }
            if(i==n)ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

F.Asya And Kittens （启发式合并 or ripe黑科技 or 链表操作）

题意

给你n-1对，相邻的在一块，选了这两个数，这两个集合就可以看成一个集合了，问符合条件的序列。

思路

很容易想到并查集的合并操作，对于一次合并相当于把两个集合变成了一块，那么现在的问题就是怎么处理集合合并

方法有三，

1.启发式合并，每次把容量小的合并到容量大的里面去，这样可以保证复杂度是log

2.链表，这样直接把头指针插到另一个的尾指针上，每一个的操作复杂度为o(1)

3.rope 黑科技，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int fa[maxn];
vector<int>G[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        fa[i]=i;G[i].push_back(i);
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        int fx=fa[x],fy=fa[y];
        if(G[fx].size()<G[fy].size())swap(fx,fy);
        for(int j=0;j<G[fy].size();j++){
            G[fx].push_back(G[fy][j]);
            fa[G[fy][j]]=fx;
        }
        G[fy].clear();
    }
    for(int i=0;i<n;i++){
        cout<<G[fa[1]][i]<<" ";
    }
    return 0;
}

rope

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#include<ext/rope>
using namespace __gnu_cxx;
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
rope<int>a[maxn];
int fa[maxn];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        a[i].push_back(i);
        fa[i]=i;
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        x=find(x),y=find(y);
        a[x]+=a[y];
        fa[y]=x;
    }
    for(int i=1;i<=n;i++){
        if(find(i)==i){
            for(int j=0;j<a[i].size();j++)cout<<a[i][j]<<" ";
        }
    }
    return 0;
}